Computer Science - Computational Complexity
Subcategories
Papers
Complexity Classes as Mathematical Axioms
M. Freedman • (2009) • DOI:
10.48550/arXiv.0810.0033
Treating a conjecture, P^#P != NP, on the separation of complexity classes as an axiom, an implication is found in three manifold topology with little obvious connection to complexity theory. This is ...
NP-complete Problems and Physical Reality
Scott Aaronson • (2005) • DOI:
10.48550/arXiv.quant-ph/0502072
Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, qu...